In computational geometry, a bitonic tour of a set of point sites in the Euclidean plane is a closed polygonal chain that has each site as one of its vertices, such that any vertical line crosses the chain at most twice.
The optimal bitonic tour is a bitonic tour of minimum total length. It is a standard exercise in dynamic programming to devise a polynomial time algorithm that constructs the optimal bitonic tour.[1] The optimal bitonic tour may be used as a heuristic solution to the traveling salesman problem, however its length may be larger than that of the optimal traveling salesman tour.[2]
At the 5th International Olympiad in Informatics, in Mendoza, Argentina in 1993, one of the contest problems involved bitonic tours: the contestants were to devise an algorithm that took as input a set of sites and a collection of allowed edges between sites and construct a bitonic tour using those edges that included as many sites as possible. As with the optimal bitonic tour, this problem may be solved by dynamic programming.[3]
The optimal bitonic tour has no self-crossings, because any two edges that cross can be replaced by an uncrossed pair of edges with shorter total length.